home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1995 April / Internet Tools.iso / infoserv / wais / ir-book-sources / mphf / vheap.c.Z / vheap.c
Encoding:
C/C++ Source or Header  |  1993-04-07  |  9.6 KB  |  358 lines

  1. /****************************  vheap.c  **********************************
  2.  
  3.    Purpose:    Implement a "virtual heap": a combination of stacks and
  4.            a heap.
  5.  
  6.    Provenance:    Written and tested by Q. Chen and E. Fox, March 1991.
  7.            Edited and tested by S. Wartik, April 1991.
  8.         Revised and tested by S. Wartik, July 1991.
  9.  
  10.    Notes:    The point of the combination is that a stack is a more
  11.            efficient data structure.  Vertices of low degree
  12.         (specifically, those <= NO_STACKS) are stored in stacks,
  13.         since they are more common.  Vertices of high degree are
  14.         stored in the heap.
  15.  
  16. **/
  17.  
  18. #include <math.h>
  19. #include <stdio.h>
  20.  
  21.    /* The following aims to define INT_MAX as the maximum value of
  22.     * type "int" for the hardware on which the program is being compiled.
  23.     */
  24. #ifdef __STDC__
  25. #include <limits.h>
  26. #else
  27.    /* According to a comment in the file "values.h" on a Sun-4 (which
  28.     * unfortunately isn't widely available), the following works on any
  29.     * binary representation where the high-order bit contains the sign.
  30.     */
  31. #   ifndef INT_MAX
  32. #    if gcos
  33. #        define    BITSPERBYTE 9
  34. #    else
  35. #        define    BITSPERBYTE 8
  36. #    endif
  37. #    define BITS(type)    (BITSPERBYTE * (int)sizeof(type))
  38. #    define HIBITI        (1 << BITS(int) - 1)
  39. #    define INT_MAX        (~HIBITI)
  40. #   endif
  41. #endif
  42.  
  43. #include "types.h"
  44. #include "support.h"
  45. #include "vheap.h"
  46.  
  47.  
  48. #define NO_STACKS 6       /* The number of stacks in use.           */
  49. #define DEF_SIZE 10       /* The default size of a heap or a stack. */
  50.  
  51. typedef struct {             /* Stack data structure.               */
  52.    int stackTop,             /* Stack top.                          */
  53.        stackSize;            /* Allocated stack area size.          */
  54.    vertexType **stackRep;    /* Stack area.                         */
  55. } stackType;
  56.  
  57. typedef struct {             /* Heap cell data structure.        */
  58.    int degree;               /* Key field, containing vertex's degree.    */
  59.    vertexType *vertex;       /* Info field, holding vertex's address.    */
  60. } heapCell;
  61.  
  62. typedef struct {             /* Heap data structure.             */
  63.    int     heapTop,             /* Heap top.                        */
  64.         heapSize;            /* Allocated heap area size.        */
  65.    heapCell *heapRep;        /* Heap area.                       */
  66. } heapType;
  67.  
  68. stackType    stacks[NO_STACKS];   /* The stacks of the virtual heap.    */
  69. heapType    heap;             /* The heap portion.        */
  70.  
  71. #ifdef __STDC__
  72.  
  73. extern void    push( stackType *stack, vertexType *vertex );
  74. extern int    pop( stackType *stack, vertexType **vertex );
  75. extern void    enter_heap( int degree, vertexType *vertex );
  76. extern int    remove_from_heap( vertexType **vertex );
  77.  
  78. #else
  79.  
  80. extern void    push();
  81. extern int    pop();
  82. extern void    enter_heap();
  83. extern int    remove_from_heap();
  84.  
  85. #endif
  86.  
  87.  
  88.  
  89. /***********************************************************************
  90.  
  91.       add_to_vheap( vertex, degree )
  92.  
  93.   Return:    void
  94.  
  95.   Purpose:    Add a vertex of a specified degree to the virtual heap.    
  96.  
  97. **/
  98.  
  99. void add_to_vheap( vertex, degree )
  100.     vertexType         *vertex;        /* in: a vertex to be added.    */
  101.     int             degree;        /* in: the vertex's degree.        */
  102. {
  103.     if ( degree > NO_STACKS )
  104.     enter_heap( degree, vertex );
  105.     else
  106.     push( &stacks[degree-1], vertex );
  107. }
  108.  
  109. /*************************************************************************
  110.  
  111.     max_degree_vertex( vertex )
  112.  
  113.   Return:    int -- NORM if a vertex could be found, ABNORM if the
  114.           virtual heap (stacks and heap) is empty.
  115.         
  116.   Purpose:    Find the unvisited vertex with maximal degree from the
  117.         virtual heap.  Place it in "vertex".
  118.  
  119.   Plan:        First check the heap; remove_from_heap() automatically
  120.           removes a vertex of maximal degree.  If the heap is
  121.         empty, try the stacks, one at a time.
  122. **/
  123.  
  124. int max_degree_vertex( vertex )
  125.    vertexType    **vertex;        /* out: the vertex found. */
  126. {
  127.     int    i;
  128.  
  129.     if ( remove_from_heap( vertex ) == NORM ) /* heap empty? */ 
  130.     return(NORM);
  131.  
  132.     for( i = NO_STACKS - 1; i >= 0; i-- )        /* stacks empty? */
  133.     if ( pop( &stacks[i], vertex ) == NORM )
  134.         return (NORM);
  135.  
  136.     return(ABNORM);     /* No node at all. The component has been processed. */
  137. }
  138.  
  139.  
  140. /*************************************************************************
  141.  
  142.     push(stack, vertex )
  143.  
  144.   Return:    void
  145.   
  146.   Purpose:    Push a vertex pointer onto a stack.
  147. **/
  148.  
  149. static void push(stack, vertex)
  150.     stackType    *stack;      /* in out: the stack.    */
  151.     vertexType    *vertex;     /* in: the vertex.        */
  152. {
  153.     stack->stackTop++;
  154.  
  155.     /* Expand stack if it doesn't have enough space. */
  156.     if ( stack->stackTop >= stack->stackSize ) {
  157.     fprintf(stderr, "Warning: stack overflow. Re-allocating.\n");
  158.     stack->stackSize *= 2;
  159.     stack->stackRep =
  160.         (vertexType**)ownrealloc( (char *)stack->stackRep,
  161.                     sizeof(vertexType*) * stack->stackSize );
  162.     }
  163.  
  164.     stack->stackRep[stack->stackTop] = vertex;
  165. }
  166.  
  167.  
  168. /*************************************************************************
  169.  
  170.     pop( stack, vertex )
  171.  
  172.   Return:    int -- Index of a vertex.
  173.   
  174.   Purpose:    Pop up a vertex pointer from the stack.  Return -1 if the stack
  175.             was empty, 0 if it wasn't.
  176. **/
  177.  
  178. static int pop( stack, vertex )
  179.     stackType    *stack;
  180.     vertexType    **vertex;
  181. {
  182.     if ( stack->stackTop == -1 )
  183.     return(-1);      /* stack empty */
  184.  
  185.     *vertex = stack->stackRep[stack->stackTop--];
  186.     return(0);       /* stack not empty */
  187. }
  188.  
  189. /*************************************************************************
  190.  
  191.     enter_heap( degree, vertex )
  192.  
  193.   Return:    void
  194.   
  195.   Purpose:    Insert a vertex pointer and its degree into the heap.
  196.  
  197. **/
  198.  
  199. static void enter_heap( degree, vertex )
  200.     int        degree;      /* in: the degree of the node.    */
  201.     vertexType    *vertex;     /* in: the vertex pointer.        */
  202. {
  203.     int k = heap.heapTop++ ;
  204.  
  205.     if ( k >= heap.heapSize ) {
  206.     heap.heapSize = 2 * heap.heapSize;
  207.     heap.heapRep =
  208.         (heapCell*)ownrealloc( (char *)heap.heapRep,
  209.                     sizeof(heapCell) * heap.heapSize );
  210.     }
  211.  
  212.     heap.heapRep[k].degree = degree;
  213.     heap.heapRep[k].vertex = vertex;
  214.  
  215.     while ( heap.heapRep[k/2].degree <= degree ) {
  216.     heap.heapRep[k].degree = heap.heapRep[k/2].degree;
  217.     heap.heapRep[k].vertex = heap.heapRep[k/2].vertex;
  218.     k /= 2;
  219.     }
  220.  
  221.     heap.heapRep[k].degree = degree;
  222.     heap.heapRep[k].vertex = vertex;
  223. }
  224.  
  225.  
  226. /*************************************************************************
  227.  
  228.     remove_from_heap( vertex )
  229.  
  230.   Return:    int -- -1 if the heap is empty when the routine is called,
  231.           0 if it isn't.
  232.  
  233.   Purpose:    Remove a vertex of maximal degree from the heap, and
  234.           return it.
  235. **/
  236.  
  237. static int remove_from_heap( vertex )
  238.     vertexType    **vertex;   /* out: the vertex selected.    */
  239. {
  240.     int        k, j;        /* Iterators through the heap.            */
  241.     heapCell    tempCell;    /* Heap element currently being examined.    */
  242.  
  243.     if ( heap.heapTop == 1 ) return(-1);
  244.  
  245.     *vertex = heap.heapRep[1].vertex;
  246.     heap.heapTop--;
  247.  
  248.     tempCell.degree =
  249.     heap.heapRep[1].degree= heap.heapRep[heap.heapTop].degree;
  250.     tempCell.vertex = heap.heapRep[1].vertex =
  251.     heap.heapRep[heap.heapTop].vertex;
  252.  
  253.     k = 1;                                        /* Go down the heap. */
  254.     while ( k <= heap.heapTop / 2 ) {
  255.     j = 2 * k;
  256.     if ( (j < heap.heapTop ) &&
  257.         (heap.heapRep[j].degree< heap.heapRep[j+1].degree) )
  258.         j++;
  259.     if ( tempCell.degree > heap.heapRep[j].degree )
  260.         break;
  261.     heap.heapRep[k].degree = heap.heapRep[j].degree;
  262.     heap.heapRep[k].vertex = heap.heapRep[j].vertex;
  263.     k = j;
  264.     }  /* end of while */
  265.  
  266.     heap.heapRep[k].degree = tempCell.degree;
  267.     heap.heapRep[k].vertex = tempCell.vertex;
  268.     return(0);
  269. }
  270.  
  271.  
  272. /*************************************************************************
  273.  
  274.     initialize_vheap()
  275.  
  276.   Return:    void
  277.   
  278.   Purpose:    Set the heap and stacks to their empty states.
  279. **/
  280.  
  281. void initialize_vheap()
  282. {
  283.     int    i;
  284.  
  285.     heap.heapRep[0].degree = INT_MAX;
  286.     heap.heapTop = 1;
  287.  
  288.     for ( i = 1; i < heap.heapSize; i++ ) {
  289.     heap.heapRep[i].degree = 0;
  290.     heap.heapRep[i].vertex = 0;
  291.     }
  292.  
  293.     for ( i = 0; i < NO_STACKS; stacks[i++].stackTop = -1 );
  294. }
  295.  
  296.  
  297.  
  298. /*************************************************************************
  299.  
  300.     free_vheap()
  301.  
  302.   Return:    void
  303.   
  304.   Purpose:    Deallocate space for stacks and heap.
  305. **/
  306.  
  307. void free_vheap()
  308. {
  309.     int i;
  310.  
  311.     for ( i = 0; i < NO_STACKS; free((char *)stacks[i++].stackRep) );
  312.  
  313.     free( (char *)heap.heapRep );
  314. }
  315.  
  316.  
  317.  
  318. /*************************************************************************
  319.  
  320.     allocate_vheap( no_arcs, no_vertices )
  321.  
  322.   Return:    void
  323.   
  324.   Purpose:    Estimate and allocate space for the heap and the stacks.
  325. **/
  326.  
  327. void allocate_vheap( no_arcs, no_vertices )
  328.     int        no_arcs,               /* in: number of arcs.         */
  329.         no_vertices;           /* in: number of vertices.     */
  330. {
  331.     int        i,                         /* iteration variable.             */
  332.         sum = 0;                   /* partial sum of degree.         */
  333.     double  lambda,                    /* lambda = |E| / ( |V| / 2 )         */
  334.         Pr0,                       /* Pr0 = Pr(X = 0)                    */
  335.         Pri;                       /* Pri = Pr(X = i)                    */
  336.  
  337.     lambda = (double)(2*no_arcs) / (double)no_vertices;
  338.     Pr0 = Pri = exp(-lambda);              /* Compute Pr(x = 0). */
  339.  
  340.     for ( i = 1; i <= NO_STACKS; i++ ) {   /* Compute the expected number   */
  341.     Pri *= lambda/(double)(i);         /* of nodes of degree 1, 2, ..., */
  342.                        /* NO_STACKS.                    */
  343.     stacks[i-1].stackSize = (int) 2 * no_vertices * Pri;
  344.     sum += stacks[i-1].stackSize ;
  345.     }
  346.  
  347.     for ( i = 0; i < NO_STACKS; i++ ) {    /* Allocate stack space. */
  348.     if ( stacks[i].stackSize <= 0 ) stacks[i].stackSize = DEF_SIZE; 
  349.         stacks[i].stackRep = 
  350.           (vertexType**) owncalloc( stacks[i].stackSize, sizeof(vertexType*) );
  351.     }
  352.  
  353.     heap.heapSize = no_vertices - sum - (int) 2 * no_vertices * Pr0;
  354.     if ( heap.heapSize <= 0 ) heap.heapSize = DEF_SIZE;
  355.     heap.heapRep =                      /* Allocate heap space. */
  356.         (heapCell*) owncalloc( heap.heapSize, sizeof(heapCell) );
  357. }
  358.